#define _CRT_SECURE_NO_WARNINGS 1


//写一个二分查找函数
//功能：在一个升序数组中查找指定的数值，找到了就返回下标，找不到就返回 - 1.
//#include<stdio.h>
//int BinarySearch(int arr[10],int sz,int k)
//{
//	int left = 0;
//	int right = sz - 1;
//	while (left <= right)
//	{
//		int mid = left + (right - left) / 2;
//		if (k < arr[mid])
//		{
//			right = mid - 1;
//		}
//		else if (k > arr[mid])
//		{
//			left = mid + 1;
//		}
//		else
//			return mid;
//	}
//	return -1;
//}
//int main()
//{
//	int k = 7;
//	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	printf("%d\n", BinarySearch(arr, sz, k));
//	return 0;
//}



//实现一个函数，打印乘法口诀表，口诀表的行数和列数自己指定
//如：输入9，输出9 * 9口诀表，输出12，输出12 * 12的乘法口诀表。

//#define n 9
//void PrintTable()
//{
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			printf("%d*%d=%-4d ", j, i, i * j);
//		}
//		printf("\n");
//	}
//}
//
//#include<stdio.h>
//int main()
//{
//	PrintTable();
//	return 0;
//}




//实现函数判断year是不是润年
// 
//int is_leap_year(int year)
//{
//	if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//		return 1;
//	else
//		return 0;
//}
//#include<stdio.h>
//int main()
//{
//	int year = 0;
//	scanf("%d", &year);
//	if (is_leap_year(year))
//		printf("%d是闰年\n", year);
//	else
//		printf("%d不是闰年\n", year);
//	return 0;
//}

//实现一个函数is_prime，判断一个数是不是素数。
//利用上面实现的is_prime函数，打印100到200之间的素数。

//#include<stdio.h>
//#include<math.h>
//int is_prime(int n)
//{
//	for (int i = 2; i <= sqrt(n); i++)
//	{
//		if (n % i == 0)
//			return 0;
//	}
//	return 1;
//}
//int main()
//{
//	int n = 0;
//	for (int i = 101; i <= 199; i += 2)
//	{
//		if (is_prime(i))
//			printf("%d ", i);
//	}
//	//scanf("%d", &n);
//	//if (is_prime(n))
//	//	printf("%d是素数\n", n);
//	//else
//	//	printf("%d不是素数\n", n);
//	return 0;
//}

//第n个斐波那契数
// 递归
//int Fib(int n)
//{
//	if (n <= 2)
//		return 1;
//	else if (n > 2)
//		return Fib(n - 1) + Fib(n - 2);
//}
//#include<stdio.h>
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%d\n", Fib(n));
//	return 0;
//}
//迭代
//#include<stdio.h>
//int Fib(int n)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n - 2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		n--;
//	}
//	return c;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%d\n", Fib(n));
//	return 0;
//}

//编写一个函数实现n的k次方，使用递归实现。
//#include<stdio.h>
//int Square(int n, int k)
//{
//	if (k == 0)
//		return 1;
//	if (k > 0)
//		return n * Square(n, k - 1);
//}
//int main()
//{
//	int n = 0;
//	int k = 0;
//	scanf("%d %d", &n, &k);
//	printf("%d\n", Square(n, k));
//	return 0;
//}


//写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
//例如，调用DigitSum(1729)，则应该返回1 + 7 + 2 + 9，它的和是19
//输入：1729，输出：19

//#include<stdio.h>
//int DigitSum(int n)
//{
//	if (n <= 9)
//		return n;
//	else if (n > 9)
//	{
//		return DigitSum(n / 10) + n % 10;
//	}
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%d\n", DigitSum(n));
//	return 0;
//}


//递归和非递归分别实现求n的阶乘（不考虑溢出的问题）
//递归
//#include<stdio.h>
//int Fact(int n)
//{
//	if (n == 0)
//		return 1;
//	else if (n > 0)
//		return n * Fact(n - 1);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%d\n", Fact(n));
//	return 0;
//}

//迭代
//#include<stdio.h>
//int Fact(int n)
//{
//	int sum = 1;
//	for (int i = 1; i <= n; i++)
//	{
//		sum = sum * i;
//	}
//	return sum;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%d\n", Fact(n));
//	return 0;
//}

//递归方式实现打印一个整数的每一位
//void Print(n)
//{
//	if (n <= 9)
//		printf("%d ", n);
//	else if (n > 9)
//	{
//		Print( n / 10);
//		printf("%d ", n % 10);
//	}
//		
//}
//#include<stdio.h>
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	Print(n);
//	return 0;
//}


